namespace Chapter4
  (*
  General Discussion ( * )

  In this section we discuss the various constructs we have seen until now in the chapter.

  We will discuss how we can define types to store structured information.
  We will start with two very simple datatypes: Maybe (which we have seen already as "'a Option") and lists.
  We will see a simpler form of trees, binary trees, and a useful peculiarity of generic types which is called generic constraints.
  We will then see a representation of arithmetic expressions, and we will use units of measure to better classify them and restrict the set of accepted expressions.
  *)

  (*
  Discriminated Unions ( * )

  All the datatype definitions we will see in this section are known as "discriminated unions".
  Discriminated unions are used for those types where a valid value of the type may assume different shapes.
  For correctness we want to give a different name to each one of these shapes and to distinguish the shape of a given value of the type being defined.
  Discriminated unions are defined as follows:
  type TYPE-NAME = CONSTRUCTOR1 of PARAMS1 | CONSTRUCTOR2 of PARAMS2 | ... | CONSTRUCTORn of PARAMSn

  each constructor and its parameters represent a particular shape that the values of our datatype may take.
  *)
  module Examples =
    open System

    (*
    Choice ( * )

    We start with a very simple datatype which can either hold values of type integer of string:
    *)
    type IntOrString = Int of int | String of string

    (*
    To construct a value of such a type we have to specify a constructor and its parameters. For example, both:
    Int 10

    and
    String "hello"

    have type IntOrString

    To extract the parameters from a type, we use pattern matching:
    *)
    let to_string =
      function
      | Int i -> i.ToString()
      | String s -> s

    (*
    When pattern matching, we can also specify values.
    Suppose we are looking for very specific data:
    *)
    let look_for_one =
      function
      | Int 1 -> true
      | String "one" -> true
      | _ -> false

    (*
    A very useful discriminated union that generalizes the form seen above is Either (already defined in the F# standard libraries as Choice):
    *)
    type Either<'a,'b> = Left of 'a | Right of 'b


    (*
    Option ( * )
    Another common discriminated union is a special form of choice, where one of the choices is parameterless.
    This is a useful construct to represent those values that may be null, but the compiler will warn us whenever we forget a null check (a very proper and decent thing for a compiler to do, by the way).

    The option datatypes is also called maybe. We start by defining its version for storing only integers and we show how to build and consume values of its type:
    *)
    type MaybeInt = Just of int | Nothing
  
    let maybe_ints = [ Nothing; Just 0 ]
    let print_maybe_ints l =
      for x in l do
        match x with
        | Nothing -> Console.WriteLine("nothing")
        | Just x  -> Console.WriteLine("just " + x.ToString())

    (*
    We can give a generalized description of this datatype by using generic parameters, so that it may store values of any type.
    The F# standard library defines Option<'a> as Some of 'a and None, but other than a change of names the two definitions are essentially the same:
    *)
    type Maybe<'a> = Just of 'a | Nothing
      with
        member this.Value =
          match this with
          | Nothing -> failwith "cannot extract a value from nothing"
          | Just x  -> x
    let maybes = [ Nothing; Just "something" ]
    let print_maybes l =
      for x in l do
        match x with
        | Nothing -> Console.WriteLine("nothing")
        | Just x  -> Console.WriteLine("just " + x.ToString())


    (*
    Lists ( * )
    Defining a list datatype is very simple, since a constructor may freely use parameters of the same type being defined.
    This way we can build recursive (inductive, to be precise) datatypes.

    A list is defined as either the empty list or an element (called "head") followed by another list (called "tail"):
    *)
    type ListInt = Empty | Head of int * ListInt

    (*
    We can, ntaurally, define a generic version of lists that are capable of storing sequences of any value:
    *)
    type List<'a> = Nil | Cons of int * List<'a>

    let rec length =
      function
      | Nil -> 0
      | Cons(_,tl) -> 1 + (length tl)


    (*
    BinTree and Generic Constraints ( ** )

    The definition of a binary tree differs very little from the definition of a list, only instead of having just one tail we now have two: one for all the elements smaller than the head and another for all the elements greater than the head.
    As we have done in the previous examples, we are interested in giving a generic definition of our data structures so we do not have to rewrite them whenever we wish to use them to store a new type of value
    Unfortunately, we encounter a bit of a problem here: a binary tree may not contain values that cannot be compared.

    F# allows us to define "generic constraints", which are restrictions on type parameters (a generic constraint of sort is [<Measure>], which we have used to mark certain generic parameters that are units of measure.
    Generic constraints can be many, but for the moment we start with the simplest: comparison and equality.

    After declaring the generic type parameters between angle brackets < >, we specify zero or more constraints wihch are of the form:
    't OP CONSTRAINT

    For example,
    'a : equality

    or
    'a : comparison

    mean, respectively, that values of type 'a can be compared for equality with the ( = ) operator or that they may compared with any comparison operator such as ( > ), ( >= ), etc.
    *)
    type BinTree<'a when 'a : comparison> = Leaf | Node of 'a * BinTree<'a> * BinTree<'a>

    (*
    Having defined our binary tree with the comparison constraint on the values it contains we can now freely use any comparison operator:
    *)
    let rec insert x =
      function
      | Leaf -> Node(x,Leaf,Leaf)
      | Node(y,l,r) ->
        if y > x then Node(y,insert x l,r)
        elif y < x then Node(y,l,insert x r)
        else Node(y,l,r)

    (*
    The full list of generic constraints is the following:
    - 't :> TYPE, requires 't to be derived from or equal to TYPE, or if TYPE is an interface the 't must implement it
    - 't : null, requires that 't is a .Net type that supports to have null value; by default, .Net types support this constraint while F# types do not and use Option<'a> to represent null values
    - 't : MEMBER-SIGNATURE, requires that values of type 't support the member specified in MEMBER-SIGNATURE; this is a complex, yet powerful, form of Duck Typing
    - 't : (new : unit -> 't), requires that 't supports a parameterless constructor
    - 't : struct, forbids 't to be a reference type (C# classes are references, C# structs are not)
    - 't : not struct, the opposite of the previous constraint
    - 't : delegate<INPUT-PARAMS, RETURN>, requires 't to be a delegate (function) type
    - 't : unmanaged, requires 't to be an unmanaged type, that is a primitive type or a structure of primitive types which is usually needed for interoperating with low-level libraries through P/Invoke or other similar mechanisms
    - 't : equality
    - 't : comparison

    Member constraints can be inferred automatically. For example, if a piece of code uses comparisons and the ( + ) operator then the compiler may infer that certain type parameters have the comparison constraint and the ( + ) member constraints.
    *)

    (*
    Structs ( ** )

    The difference between structures and classes is an important, albeit very low level, construct supported by .Net languages such as C#, F# and VB .Net.
    Structures can make a large performance difference and are one of the very few ways for a managed program to communicate and share data with the underlying system.

    "Regular" datatype such as a tuple, a record or a discriminated union (or a C# class) is usually allocated on the heap.
    Accesses to its memory are done through references, and during the execution of the program the Garbage Collector may choose to move data around to compact it.

    We can define smaller values, such as vectors or pairs, as structs. Structs are allocated at the point of declaration, and are never pointers.
    This means that the memory that a struct occupies may be in the stack or inside the memory area of another class.
    Passing a struct to a function requires making a copy of it, and in general structs do not require any additional work on the part of the garbage collector, since they are not garbage collected.

    We can define, initialize and use a struct in F# as follows:
    *)
    type FastPoint =
      struct
        val mutable X : int
        val mutable Y : int
      end

    let p = FastPoint(X = 100, Y = 20000)
    let p_lengthsquared = p.X * p.X + p.Y * p.Y


    (*
    Expressions ( ** )

    Discriminated unions are also often used to represent other types of information; for example, we can use discriminated unions to represent arithmetic expressions.

    We define an arithmetic expression as a constant value, a sum of two expressions or the product of two expressions:
    *)
    type IntExpr = Const of int | Sum of IntExpr * IntExpr | Mul of IntExpr * IntExpr

    (*
    We evaluate an arithmetic expression by performing the appropriate operations on the result of the evaluation of the child expressions.
    The evaluation of a constant  expression is its value:
    *)
    let rec eval_int =
      function
      | Const i -> i
      | Sum(a,b) -> eval_int a + eval_int b
      | Mul(a,b) -> eval_int a * eval_int b


    (*
    Suppose that we wish to define expressions which may contain a mixture of integers and booleans;
    an important aspect of such a data structre is the set of limitations that forbid meaningless expressions such as sums of booleans or the logical and of two integers.

    We define two units of measure, Integer and Boolean, and we add this unit of measure to our expressions.
    This way we can require that each constructor such as Sum or Mul may only be invoked on the appropriate expressions:
    *)
    [<Measure>]
    type Integer

    [<Measure>]
    type Boolean

    type Expr< [<Measure>] 'u > =
        ConstInt of int
      | ConstBool of bool
      | Sum of Expr<Integer> * Expr<Integer>
      | Mul of Expr<Integer> * Expr<Integer>
      | And of Expr<Boolean> * Expr<Boolean>
      | Or of  Expr<Boolean> * Expr<Boolean>
      | GEq of Expr<Integer> * Expr<Integer>

    (*
    At this point we may define a series of operators to correctly invoke our constructors.
    We define the unary operators (!) and (!!) to create, respectively, an integer and boolean expression from a corresponding value.
    We also define a series of operators to sum, multiply, etc our expressions:
    *)
    let (!) i = (ConstInt i) : Expr<Integer>
    let (!!) b = (ConstBool b) : Expr<Boolean>
    let (.+) (e1:Expr<Integer>) (e2:Expr<Integer>) = (Sum(e1,e2)) : Expr<Integer>
    let (.*) (e1:Expr<Integer>) (e2:Expr<Integer>) = (Mul(e1,e2)) : Expr<Integer>
    let (.&&) (e1:Expr<Boolean>) (e2:Expr<Boolean>) = (And(e1,e2)) : Expr<Boolean>
    let (.||) (e1:Expr<Boolean>) (e2:Expr<Boolean>) = (Or(e1,e2)) : Expr<Boolean>
    let (.>=) (e1:Expr<Integer>) (e2:Expr<Integer>) = (GEq(e1,e2)) : Expr<Boolean>

    (*
    Now we can create reasonably nice-looking expressions with the above operators:
    *)
    let expr1 = (!10 .+ !20) .* !2
    let expr2 = !!true .|| !!false
    let expr3 = (expr1 .>= !1) .&& expr2

    (*
    What's possibly even more important is that unreasonable expressions such as:
    !10 .|| !!true

    will give a compile-time error, thereby letting us find mistakes more quickly and with less testing.
    *)

    (*
    At this point we can give a function to evaluate an integer expression and another to evaluate a boolean expression,
    and we can be sure that if the user has built his expression with the operators described above then we will never encounter a runtime error.
    *)
    let rec int_eval (e:Expr<Integer>) =
      match e with
      | ConstInt i -> i
      | Sum(e1,e2) -> int_eval e1 + int_eval e2
      | Mul(e1,e2) -> int_eval e1 + int_eval e2
      | _ -> failwith "Malformed expression. It is not allowed to mix integers and booleans together."

    let rec bool_eval (e:Expr<Boolean>) =
      match e with
      | ConstBool b -> b
      | And(e1,e2)  -> bool_eval e1 && bool_eval e2
      | Or(e1,e2)   -> bool_eval e1 || bool_eval e2
      | GEq(e1,e2)  -> int_eval e1 >= int_eval e2
      | _ -> failwith "Malformed expression. It is not allowed to mix integers and booleans together."
